#include <iostream>

using namespace std;

int main()
{
    int n, m; cin >> n >> m;
        
    long long output = n;
    
    while(--m)
    {
        output = (output * (n - 1)) % 109;
    }
    
    cout << output;

    return 0;
}



#include <iostream>
#include <variant>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int n, m;
int x_start, y_start, x_end, y_end;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};


bool isValid(int x, int y, vector<vector<char>>& board, vector<vector<int>>& visited){
    return x >= 0 && x < n && y >= 0 && y < m && visited[x][y] == -1 && board[x][y] == '.';
}

int bfs(vector<vector<char>>& board, vector<vector<int>>& visited){
    if(board[x_end][y_end] == '*')
        return -1;

    queue<pair<int, int>> q;
    q.push({x_start, y_start});
    visited[x_start][y_start] = 0;

    while(!q.empty()){
        auto[a, b] = q.front();
        q.pop();

        for(int i = 0; i < 4; i++){
            int x = a+dx[i];
            int y = b+dy[i];

            if(isValid(x, y, board, visited)){
                q.push({x, y});
                visited[x][y] = visited[a][b]+1;

                if(x == x_end && y == y_end)
                    return visited[x][y];
            }
        }
    }

    return -1;
}


int main(){
    cin >> n >> m;
    cin >> x_start >> y_start  >> x_end >> y_end;
    x_start--, y_start--, x_end--, y_end--;

    if(x_start == x_end && y_start == y_end){
        cout << 0;
    }
    else{
        vector<vector<int>> visited(n, vector<int>(m, -1));
        vector<vector<char>> board(n, vector<char>(m));

        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                cin >> board[i][j];
            }
        }

        cout << bfs(board, visited);
    }

    return 0;
}



// class Solution {
// public:
//     int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
//         if(startEnd.size() == 0)
//             return 0;

//         int count = 0;
//         vector<int> starts;
//         vector<int> ends;

//         for(auto v : startEnd){
//             starts.push_back(v[0]);
//             ends.push_back(v[1]);
//         }

//         sort(starts.begin(), starts.end());
//         sort(ends.begin(), ends.end());

//         int endId = 0;
//         for(int i = 0; i < startEnd.size(); ++i) {
//             // 开始时间小于结束时间，只有一种情况，就是自己的开始时间小于别人的结束时间，所以count需要++
//             if(starts[i] < ends[endId])  
//                 count++;
//             else
//                 endId++;
//         }

//         return count;
//     }
// };

class Solution {
public:
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        if(startEnd.size() == 0)
            return 0;

        sort(startEnd.begin(), startEnd.end()); 

        priority_queue<int, vector<int>, greater<int>> pq;
        pq.push(startEnd[0][1]);


        for(int i = 1; i < startEnd.size(); ++i) {
            int startTime = startEnd[i][0];
            int endTime = startEnd[i][1];
            int maxEndTime = pq.top();

            if(startTime >= maxEndTime) {  // 不会有重叠
                pq.pop();
                pq.push(endTime);          // 更新当前最大结束时间
            }
            else {
                pq.push(endTime);          // 还需要增加一个主持人
            }
        }

        return pq.size();
    }
};